Search results for "Line Graph"

Dynamic 2- and 3-connectivity on planar graphs

1992

We study the problem of maintaining the 2-edge-, 2-vertex-, and 3-edge-connected components of a dynamic planar graph subject to edge deletions. The 2-edge-connected components can be maintained in a total of O(n log n) time under any sequence of at most O(n) deletions. This gives O(log n) amortized time per deletion. The 2-vertex- and 3-edge-connected components can be maintained in a total of O(n log2n) time. This gives O(log2n) amortized time per deletion. The space required by all our data structures is O(n).

Searching for a strong double tracing in a graph

1998

Given a connected graph G, we present a polynomial algorithm which either finds a tour traversing each edge of G exactly two non-consecutive times, one in each direction, or decides that no such tour exists. The main idea of this algorithm is based on the modification of a proof given by Thomassen related to a problem proposed by Ore in 1951.

Optimal Mass Transport on Metric Graphs

2015

We study an optimal mass transport problem between two equal masses on a metric graph where the cost is given by the distance in the graph. To solve this problem we find a Kantorovich potential as the limit of $p$-Laplacian--type problems in the graph where at the vertices we impose zero total flux boundary conditions. In addition, the approximation procedure allows us to find a transport density that encodes how much mass has to be transported through a given point in the graph, and also provides a simple formula of convex optimization for the total cost.

Two graphs with a common edge

2014

Let G = G1 ∪ G2 be the sum of two simple graphs G1,G2 having a common edge or G = G1 ∪ e1 ∪ e2 ∪ G2 be the sum of two simple disjoint graphs G1,G2 connected by two edges e1 and e2 which form a cycle C4 inside G. We give a method of computing the determinant det A(G) of the adjacency matrix of G by reducing the calculation of the determinant to certain subgraphs of G1 and G2. To show the scope and effectiveness of our method we give some examples

Potential approach in marginalizing Gibbs models

1999

Abstract Given an undirected graph G or hypergraph potential H model for a given set of variables V , we introduce two marginalization operators for obtaining the undirected graph G A or hypergraph H A associated with a given subset A ⊂ V such that the marginal distribution of A factorizes according to G A or H A , respectively. Finally, we illustrate the method by its application to some practical examples. With them we show that potential approach allow defining a finer factorization or performing a more precise conditional independence analysis than undirected graph models. Finally, we explain connections with related works.

Online Edge Flow Imputation on Networks

2022

Author's accepted manuscript © 2022 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. An online algorithm for missing data imputation for networks with signals defined on the edges is presented. Leveraging the prior knowledge intrinsic to real-world networks, we propose a bi-level optimization scheme that exploits the causal dependencies and the flow conservation, respe…

Graph Connectivity, Monadic NP and built-in relations of moderate degree

1995

It has been conjectured [FSV93] that an existential secondoder formula, in which the second-order quantification is restricted to unary relations (i.e. a Monadic NP formula), cannot express Graph Connectivity even in the presence of arbitrary built-in relations.

Remarks on Partially Square Graphs, Hamiltonicity and Circumference

2001

Gray coding cubic planar maps

2016

International audience; The idea of (combinatorial) Gray codes is to list objects in question in such a way that two successive objects differ in some pre-specified small way. In this paper, we utilize beta-description trees to cyclicly Gray code three classes of cubic planar maps, namely, bicubic planar maps, 3-connected cubic planar maps, and cubic non-separable planar maps. (C) 2015 Elsevier B.V. All rights reserved.

A tabu thresholding algorithm for arc crossing minimization in bipartite graphs

1996

Acyclic directed graphs are commonly used to model complex systems. The most important criterion to obtain a readable map of an acyclic graph is that of minimizing the number of arc crossings. In this paper, we present a heuristic for solving the problem of minimizing the number of arc crossings in a bipartite graph. It consists of a novel and easier implementation of fundamental tabu search ideas without explicit use of memory structures (a tabu thresholding approach). Computational results are reported on a set of 250 randomly generated test problems. Our algorithm has been compared with the two best heuristics published in the literature and with the optimal solutions for the test proble…